package com.study.modules.algorithmStructure;

/**
 * 1.二分查找
 */
public class No01TestBinarySearch {

    public static void main(String[] args) {
        /* 二分法测试*/
        int index = binarySearch(new int[] {1, 3, 5, 6, 7, 9}, 5);
        if (index != -1) {
            System.out.println("找到了，索引为： " + index);
        } else {
            System.out.println("没找到...");
        }



    }

    /**
     * 二分查找
     * 二分法的基本思想是通过将数组分成两部分来确定目标元素可能存在的位置，
     * 然后不断缩小查找范围，直到找到目标元素或者确定目标元素不存在。
     *
     * @param arr 数组
     * @param target 查找的目标
     * @return -1 没找到，否则返回索引
     */
    public static int binarySearch(int[] arr, int target) {
        // 定义左右边界
        int left = 0;
        int right = arr.length - 1;

        // 循环查找
        while (left <= right) {
            // 计算中间索引
            int mid = (left + right) / 2;

            // 判断是否找到
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1; // 没找到
    }


}
